#include <iostream>
#include <vector>

using namespace std;

/**
 * Definition for a binary tree node.
 */
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};



// 错误原因：
// 例如示例一：3->5 这条路径被计算了两次
class Solution {
public:
    vector<vector<int>> paths; // 记录所有的的路径
    
    void dfs(TreeNode* root, vector<int> &path, int cur){
        if (!root) {
            return;
        }  

        path.push_back(root->val);
        cur = cur + root->val;

        if (!root->left && !root->right) {
            paths.push_back(path);
            // 就算是得到了结果，也需要恢复现场。
            path.pop_back();
            cur -= root->val;
            return;
        }
        dfs(root->left, path, cur);
        dfs(root->right, path, cur);
        // 恢复现场
        cur -= root->val;
        path.pop_back();
    }
    
    int check(vector<int> nums, int target) {
        cout << "=========" << endl;
        int n = nums.size();
        int res = 0;

        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j ++) {
                int cur = 0;
                for (int k = i; k <= j; k++) {
                    cur += nums[k];
                }

                if (cur == target) {
                    cout << i << " " << j << endl;
                    res++;
                }
            }
        }

        cout << res << endl;
        return res;
    }


    int pathSum(TreeNode* root, int targetSum) {
        vector<int> path;
        dfs(root, path, 0);

        int res = 0;
        for (int k = 0; k < paths.size(); k++) {
            // // 滑动窗口; 检测paths[k]中连续子数组和等于targetSum的个数。
            res += check(paths[k], targetSum);

            // for (int i = 0; i < paths[k].size(); i++) {
            //     cout << paths[k][i] << " ";
            // }
            // cout << endl;
        }

        return res;
    }
};